package org.example.myleet.p731;

public class MyCalendarTwo {

    private SegmentTree segmentTree;

    public MyCalendarTwo() {
        segmentTree = new DynamicSplitSegmentTree(0, 1000000000);
    }

    public boolean book(int start, int end) {
        int val = segmentTree.query(start, end - 1, null);
        if (val >= 2) {
            return false;
        }
        segmentTree.add(start, end - 1, 1, null);
        return true;
    }

    static class DynamicSplitSegmentTree implements SegmentTree {
        Segment root;

        /**
         * 定义线段树控制的范围
         * @param leftBorder 范围的左端点
         * @param rightBorder 范围的右端点
         */
        public DynamicSplitSegmentTree(int leftBorder, int rightBorder) {
            root = new Segment(leftBorder, rightBorder);
        }

        /**
         * 查询区间中的最大值
         */
        @Override
        public int query(int l, int r, Segment segment) {
            if (l > r) {
                return 0;
            }
            if (null == segment) {
                segment = root;
            }
            if (l <= segment.l && segment.r <= r) {
                //查询的范围覆盖了整个线段，则查询结果为线段的值
                return segment.v;
            }
            //查询的范围没有覆盖到整个线段，此时需要根据线段的左节点和右节点的值确定查询范围的结果
            pushDown(segment);
            int v = 0;
            if (l <= segment.mid) {
                //查询范围覆盖到左节点
                v = Math.max(v, query(l, r, segment.left));
            }
            if (r > segment.mid) {
                //查询范围覆盖到右节点
                v = Math.max(v, query(l, r, segment.right));
            }
            return v;
        }

        @Override
        public void add(int l, int r, int v, Segment segment) {
            if (l > r) {
                return;
            }
            if (null == segment) {
                segment = root;
            }
            if (l <= segment.l && segment.r <= r) {
                //更新的范围覆盖了整个线段，则直接修改线段的值，并标记add标签
                segment.v += v;
                segment.add += v;
                return;
            }
            //更新的范围没有覆盖到整个线段，此时需要根据更新范围对应更新线段的左节点和右节点的值
            pushDown(segment);
            if (l <= segment.mid) {
                //更新范围覆盖到左节点，修改左节点的值
                add(l, r, v, segment.left);
            }
            if (r > segment.mid) {
                //更新范围覆盖到右节点，修改左右点的值
                add(l, r, v, segment.right);
            }
            //根据左节点和右节点的值更新本范围内的值
            pushUp(segment);
        }

        @Override
        public void pushDown(Segment segment) {
            if (segment.l == segment.r) {
                //已经是叶子节点，无需继续劈开范围
                return;
            }
            if (null == segment.left) {
                segment.left = new Segment(segment.l, segment.mid);
            }
            if (null == segment.right) {
                segment.right = new Segment(segment.mid + 1, segment.r);
            }
            if (0 != segment.add) {
                //存在线段范围内的值需要更新，则传递到子节点上
                segment.left.v += segment.add;
                segment.right.v += segment.add;
                segment.left.add += segment.add;
                segment.right.add += segment.add;
                //传递完成，线段的值更新标签归零
                segment.add = 0;
            }
        }

        @Override
        public void pushUp(Segment segment) {
            //根据题意，线段的值取线段范围内的最大值
            segment.v = Math.max(segment.left.v, segment.right.v);
        }
    }

    interface SegmentTree {

        /**
         * 更新l到r范围内的值，时间复杂度O(log(n))
         * @param l 范围左端点
         * @param r 范围右端点
         * @param v 更新的值
         * @param segment 递归时使用的线段
         */
        void add(int l, int r, int v, Segment segment);

        /**
         * 查询l到r范围内最大值，时间复杂度O(log(n))
         * @param l 范围左端点
         * @param r 范围右端点
         * @param segment 递归时使用的线段
         * @return l到r范围内最大值
         */
        int query(int l, int r, Segment segment);

        /**
         * 劈开线段，为线段创造左节点和右节点
         * @param segment 需要劈开的线段
         */
        void pushDown(Segment segment);

        /**
         * 基于左右子节点更新线段范围的值
         * @param segment 需要更新值的线段范围
         */
        void pushUp(Segment segment);
    }

    static class Segment {
        //线段范围内的值
        int v;
        //线段范围内的值变更标签
        int add;
        //线段范围边界
        int l;
        int r;
        //线段范围中间点
        int mid;
        //子线段节点，[l,mid]和[mid+1,r]
        Segment left;
        Segment right;

        public Segment(int l, int r) {
            this.l = l;
            this.r = r;
            this.mid = (l + r) >> 1;
            this.v = 0;
            this.add = 0;
        }
    }
}
